/*
 * @LastEditTime: 2023-03-23 20:35:30
 * @Method: 
 * @Description: 
 */
package Preview.tengxunyinyue;

import java.util.*;


public class TreeNode {
   int val = 0;
   TreeNode left = null;
   TreeNode right = null;
   public TreeNode(int val) {
     this.val = val;
   }
}


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return TreeNode类
     */

    public int[] getNum (TreeNode root) {
        int odd = 0;
        int even = 0;
        int k = 1;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            if (k % 2 == 1) {
                odd += size;
                k++;
            } else {
                even += size;
                k++;
            }
            for (int i = 0;i < size;i++) {
                TreeNode t = q.poll();
                if (t.left != null) {
                    q.offer(t.left);
                }
                if (t.right != null) {
                    q.offer(t.right);
                }
            }
        }
        return new int[]{odd, even};
    }

    public TreeNode fun (TreeNode root) {
        int[] t = getNum(root);
        int n = t[0] + t[1];
        int sum = n * (n + 1) / 2;
        sum /= 2;
        // int[] nums = new int[]{3, 1, 2};
        // int index = 0;

        HashSet<Integer> s = new HashSet<>();
        for (int i = 1;i <= n;i++) {
            s.add(i);
        }
        LinkedList<Integer> list = new LinkedList<>(s);
        int index = 0;

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0;i < size;i++) {
                TreeNode node = q.poll();
                node.val = list.get(index++);
                // index = (index + 1) % nums.length;
                if (node.left != null) {
                    q.offer(node.left);
                }
                if (node.right != null) {
                    q.offer(node.right);
                }
            }
        }
        return root;
    }
}